package l.l.w.CodingInterviews;

/**
 * Created by llw on 2018/2/28.
 * 给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。
 */
public class _66Problem {
    /**
     * 有额外的存储空间。
     * C[i] = C[i-1] * A[i-1];D[i] = D[i+1]*A[i+1];B[i]=C[i]*D[i]
     * @param A
     * @return
     */
    public int[] multiply1(int[] A) {
        if(A == null) return null;
        int len = A.length;
        int[] result = new int[len];
        int[] C = new int[len];
        int[] D = new int[len];
        C[0] = 1;
        for(int i = 1; i < len; ++i){
            C[i] = C[i-1] * A[i-1];
        }
        D[len-1] = 1;
        for(int i = len - 2; i >= 0; --i){
            D[i] = D[i+1] * A[i+1];
        }
        for(int i = 0 ; i < len; ++i){
            result[i] = C[i] * D[i];
        }
        return result;
    }

    /**
     * 方法还是按照上面的，但是可以简化。
     * 其中C可以直接使用result，后面的话用result *= XXXXX即可。然后D也可以去掉，因为在求D的循环中可以直接将相应的result[i]求出，所以只是用一个int型变量即可。
     * @param A
     * @return
     */
    public int[] multiply(int[] A){
        if(A == null) return null;
        int len = A.length;
        int[] result = new int[len];
        result[0] = 1;
        for (int i = 1; i < len; ++i){
            result[i] = result[i-1] * A[i-1];
        }
        int temp = 1;
        for(int i = len - 2; i >= 0; --i){
            temp *= A[i+1];
            result[i] *= temp;
        }
        return result;
    }
}
